package com.lw.leetcode.arr.b;

/**
 * 481. 神奇字符串
 *
 * @Author liw
 * @Date 2021/9/25 15:46
 * @Version 1.0
 */
public class MagicalString {


    public static void main(String[] args) {
        MagicalString test = new MagicalString();

        // 1221121221221121122
        // 12211212212211211221
        long l1 = System.currentTimeMillis();
        for (int i = 79999; i <= 100000; i++) {
            int i1 = test.magicalString(i);

        }

        long l2 = System.currentTimeMillis();
//        for (int i = 79999; i <= 100000; i++) {
//            int i2 = test.magicalString2(i);
//        }
        long l3 = System.currentTimeMillis();

        System.out.println(l2 - l1);
        System.out.println(l3 - l2);
    }


    public int magicalString(int n) {
        if (n < 4) {
            return 1;
        }
        if (n < 6) {
            return n - 2;
        }
        int[] arr = new int[n];
        int h = 0;
        int d = 1;
        int item = 1;
        boolean flag = true;
        arr[0] = 2;
        int sum = 5;
        int count = 3;
        while (true) {
            int p = arr[h++];
            arr[d++] = item;
            flag = !flag;
            sum += item;
            if (flag) {
                if (sum == n) {
                    return count + item;
                }
                if (sum > n) {
                    return count + 1;
                }
                count += item;
            } else {
                if (sum >= n) {
                    return count;
                }
            }
            if (p == 2) {
                arr[d++] = item;
                flag = !flag;
                sum += item;
                if (flag) {
                    if (sum == n) {
                        return count + item;
                    }
                    if (sum > n) {
                        return count + 1;
                    }
                    count += item;
                } else {
                    if (sum >= n) {
                        return count;
                    }
                }
            }
            item = item == 1 ? 2 : 1;
        }
    }


    public int magicalString2(int n) {
        if (n <= 3) return 1;
        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 2;
        int res = 1;
        int idx = 1;
        int l = 1;
        while (true) {
            int next = 3 - arr[idx - 1];
            for (int i = 0; i < arr[l]; i++) {
                arr[idx++] = next;
                if (next == 1) res++;
                if (idx == n) break;
            }
            if (idx == n) break;
            l++;
        }
        return res;
    }
}
